// Problem 046: Goldbach's other conjecture
// It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
// 9 = 7 + 2×12
// 15 = 7 + 2×22
// 21 = 3 + 2×32
// 25 = 7 + 2×32
// 27 = 19 + 2×22
// 33 = 31 + 2×12
// It turns out that the conjecture was false.
// What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

package main

import (
	"fmt"
	"math"
	"projecteuler/euler"
)

func p046() {
	for ocn := 9; ocn < 10000; ocn += 2 {
		if euler.IsPrime(ocn) {
			continue
		}
		s := int(math.Sqrt(float64(ocn / 2)))
		for ; s >= 1; s-- {
			if euler.IsPrime(ocn - 2*s*s) {
				break
			}
		}
		if s == 0 {
			fmt.Println("Problem 046:", ocn)
			return
		}
	}
}
